package com.shr.code_interview;

import java.util.ArrayList;

public class Solution_37 {
	public ArrayList<String> Permutation(String str) {
		ArrayList<String> list = new ArrayList<>();
        if(str != null && str.length() != 0){
            int i = 0;
			Perm(str, i, list) ;
        }
		return list;
	}

	/**
	 * 
	 * @param str
	 * @param i 交换开始的位置；当前的第一位
	 * @param list
	 */
	private void Perm(String str, int i, ArrayList<String> list) {
		if(i >= str.length()){
			if(!list.contains(str))
				list.add(str) ;
		}
		else{
			for(int k = i;k<str.length();k++){
				str = exchange(str, i , k) ;//改变当前第一位的元素
				Perm(str, i+1, list) ;
				str = exchange(str, k, i); //换回来
			}
		}
	}


	private String exchange(String str, int i, int k) {
		StringBuffer sb = new StringBuffer(str) ;
		char chk = sb.charAt(k) ;
		sb.deleteCharAt(k) ;
		sb.insert(i, chk) ;
		return sb.toString();
		
	}
}
